package competition;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: competition
 * @Author: 江岸
 * @CreateTime: 2021-04-11 10:29
 * @Description:
 */
public class Week236 {

    public int arraySign(int[] nums) {
        int index = 0;
        int f=0;
        for (int i=0;i<nums.length;i++){
            if (nums[i]==0){
                return 0;
            }
            if (nums[i]<0){
                f++;
            }
        }
        if (f%2==0){
            return 1;
        }
        return -1;
    }

    //约瑟夫环问题
    public int findTheWinner(int n, int k) {
        Deque<Integer> que = new LinkedList<>();
        for (int i=1;i<=n;i++){
            que.add(i);
        }
        int i=1;
        while (que.size()>1){
            if (i==k){
                que.pollFirst();
                i=1;
            }else {
                que.addLast(que.pollFirst());
                i++;
            }
        }
        return que.peekFirst();
    }

    //动态规划
    public int minSideJumps(int[] obstacles) {
        int[][] dp = new int[obstacles.length+1][3];
        for (int j=dp.length-2;j>=0;j--){
            if (j<obstacles.length){
                if (obstacles[j]!=0){
                    dp[j][obstacles[j]-1] = Integer.MAX_VALUE;
                }
            }
            for (int i=0;i<3;i++){
                //当前点的每条跑道
                if (dp[j][i]!=Integer.MAX_VALUE){
                    if (dp[j+1][i]==Integer.MAX_VALUE){
                        //下一个是石头.且这一行除了自己有石头，那么就是剩余的那个+1
                        if (i==0){
                            if (dp[j][1]==Integer.MAX_VALUE){
                                dp[j][2] = dp[j+1][2];
                                dp[j][0] = dp[j+1][2]+1;
                            }else if (dp[j][2]==Integer.MAX_VALUE){
                                dp[j][1] = dp[j+1][1];
                                dp[j][0] = dp[j+1][1]+1;
                            }else {
                                dp[j][0] = Math.min(dp[j+1][1],dp[j+1][2])+1;
                            }
                            continue;
                        }
                        if (i==1){
                            if (dp[j][2]==Integer.MAX_VALUE){
                                dp[j][0] = dp[j+1][0];
                                dp[j][1] = dp[j+1][0]+1;
                            }else if (dp[j][0]==Integer.MAX_VALUE){
                                dp[j][2] = dp[j+1][2];
                                dp[j][1] = dp[j+1][2]+1;
                            }else {
                                dp[j][1] = Math.min(dp[j+1][0],dp[j+1][2])+1;
                            }
                            continue;
                        }
                        if (i==2){
                            if (dp[j][0]==Integer.MAX_VALUE){
                                dp[j][1] = dp[j+1][1];
                                dp[j][2] = dp[j+1][1]+1;
                            }else if (dp[j][1]==Integer.MAX_VALUE){
                                dp[j][0] = dp[j+1][0];
                                dp[j][2] = dp[j+1][0]+1;
                            }else {
                                dp[j][2] = Math.min(dp[j+1][1],dp[j+1][0])+1;
                            }
                            continue;
                        }
                    }else {
                        dp[j][i] = dp[j+1][i];
                    }
                }
            }
        }
        return Math.min(dp[0][0]+1,Math.min(dp[0][1],dp[0][2]+1));
    }

    /** 贪心算法
     *   1.当青蛙所在跑道没有障碍时，可以一直向前移动，直到遇到该跑道的第一个障碍，此时需要测跳，有两个跑道供选择（other和another）。
     * 2.选择测跳跑道的依据为：青蛙跳到该跑道后遇到的第一个障碍的位置，哪条跑道的障碍越靠后就选则哪条。
     *
     * 作者：helloworld-62
     * 链接：https://leetcode-cn.com/problems/minimum-sideway-jumps/solution/tan-xin-jiu-hao-by-helloworld-62-1eum/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
}
